package Hash.Medium;

import java.util.HashMap;

public class LC0128 {
    /**
     * 思路：每遇到一个未访问的数字，向两边搜寻连续的数字是否存在，并将搜寻过的数字设置为已访问。这样可以确保彻底地搜寻一列连续的数字，并且后面遇到此列数字中的某一个时，不会重复计算。
     * 判断一个数字是否存在，可以用哈希。
     */
    public int longestConsecutive(int[] nums) {
        int N = nums.length;
        boolean[] visited = new boolean[N];
        HashMap<Integer, Integer> numIndexMap = new HashMap<>();

        for (int i = 0; i < N; i++) {
            if (numIndexMap.containsKey(nums[i])) {
                visited[i] = true; // 重复数字，这个数字我们后面就认为不存在
            }
            else numIndexMap.put(nums[i], i);
        }

        int maxLength = 0;
        for (int i = 0; i < N; i++) {
            if (visited[i]) continue;
            int num = nums[i];
            int length = 1;
            // 向两端寻找连续的数字
            for (int left = num - 1; ; left--) {
                Integer index = numIndexMap.get(left);
                if (index == null) break;
                visited[index] = true;
                length++;
            }
            for (int right = num + 1; ; right++) {
                Integer index = numIndexMap.get(right);
                if (index == null) break;
                visited[index] = true;
                length++;
            }

            maxLength = Math.max(maxLength, length);
        }

        return maxLength;
    }
}
